﻿#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "defines.h"

#include "index.h"

#define	IMAGE_IDX_NODES_HORIZON_SIZE		4
#define	IMAGE_FREE_IDX_NODES_HORIZON_SIZE	4
#define	IMAGE_HT_TABLE_SIZE			524288		/* 131072*4 */	
#define	IMAGE_IDX_NODES_SIZE			280000000	/* 7*4*1000*10000 */
#define	IMAGE_FREE_IDX_NODES_SIZE		400096		/*FIXME: 100024*4  10000000*4 */	
/* total 274341 */

#define	IMAGE_IDX_NODES_HORIZON			0
#define	IMAGE_FREE_IDX_NODES_HORIZON		4
#define	IMAGE_HT_TABLE				8
#define	IMAGE_IDX_NODES				524296
#define	IMAGE_FREE_IDX_NODES			280524296

#if defined KVS_TEST
	#define	HT_TABLE_MOD	KVS_TEST
#else
	#define	HT_TABLE_MOD	131071
#endif
#define	HT_TABLE_SIZE		131072

typedef struct
{
	HASH		hash_2, hash_3;
	PTR_DISK	disk_loc;
	int		last_slot_info;
	int		slot_cnt;
	PTR_KW		left_ptr, right_ptr;
} IDX_NODE;
/* IDX_NODE operations: (inline)*/
static	HASH		_get_hash_2(PTR_KW);
static	HASH		_get_hash_3(PTR_KW);
static	PTR_KW		_get_left(PTR_KW);
static	PTR_KW		_get_right(PTR_KW);
static	PTR_DISK	_get_loc(PTR_KW);
static	int		_get_slot_cnt(PTR_KW);
static	int		_get_last_info(PTR_KW);
static	void 		_set_node_left(PTR_KW cur_ptr, PTR_KW new_ptr);
static	void		_set_node_right(PTR_KW cur_ptr, PTR_KW new_ptr);
static	void		_set_node_left_null(PTR_KW);
static	void		_set_node_right_null(PTR_KW);
static	void 		fill_idx_node(PTR_KW, HASH, HASH, PTR_DISK, int slot_cnt, int last_slot_info);


static	FILE*		log_file=NULL;	
static	char*		image_index=NULL;

/***************************************************************/
/*Point to image_index */
/*CHANGE: --> On-the-fly change */
static	PTR_KW*		ht_table=NULL;  
static	IDX_NODE* 	idx_nodes=NULL;
static	PTR_KW*		idx_nodes_horizon=NULL;
static	PTR_KW*		free_idx_nodes=NULL;
static	PTR_KW*		free_idx_nodes_horizon=NULL;
/***************************************************************/


/***************************************************************/
/* pay attention to: reuse, re_init. */
static	PTR_KW		cur_ptr;
static	PTR_KW		pre_ptr, next_ptr;
static	HASH		hash_2, hash_3; 
static	HASH		cur_hash_2, cur_hash_3;
static	int		dir;
/***************************************************************/


/*
 * _search_by_hash()
 * INPUT:  cur_ptr, pre_ptr, hash_X  ( XXX: cur_ptr must NOT be PTR_KW_NULL )
 * OUTPUT: cur_ptr, pre_ptr, next_ptr
 *	   cur_hash
 */
static	void		_search_by_hash();
static	int		_cmp();

static	PTR_KW		_get_free_idx_node();
static	void		_put_free_idx_node(PTR_KW* _ptr);
	HASH		hash_func_1(char* key, int key_len);
	HASH		hash_func_2(char* key, int key_len);
	HASH		hash_func_3(char* key, int key_len);

STATE idx_init(INIT_TYPE init_type, char* image, const char* index_log_file)
{
	int i;
	assert(image);
	
	image_index=image;

	/* open index_log */
	if (index_log_file)
	{
		log_file=fopen(index_log_file, "w");
		if (log_file==NULL)
		{
			printf ("error no: Create %s failed\n", index_log_file);
			return IDX_INIT_FAIL;
		}
	}
	else
	{
		printf ("INDEX:no index log file.\n");
	}
		
	ht_table=(PTR_KW*)(image+IMAGE_HT_TABLE);
	idx_nodes=(IDX_NODE*)(image+IMAGE_IDX_NODES);
	idx_nodes_horizon=(PTR_KW*)(image+IMAGE_IDX_NODES_HORIZON);
	free_idx_nodes=(PTR_KW*)(image+IMAGE_FREE_IDX_NODES);
	free_idx_nodes_horizon=(PTR_KW*)(image+IMAGE_FREE_IDX_NODES_HORIZON);	

	if (init_type==INIT_TYPE_CREATE)
	{
		for (i=0; i<HT_TABLE_SIZE; i++) 
		{
            		ht_table[i]=IDX_NODE_NULL;
		}
		*idx_nodes_horizon=0;
		*free_idx_nodes_horizon=0;
	}

	if (log_file)
	{
		fprintf (log_file, "idx init type: %s\n", init_type==INIT_TYPE_LOAD?"load":"create");
		fprintf (log_file, "ht_table init test [10024]:%d\n", ht_table[10024]);
		fflush(log_file);
	}

	return IDX_INIT_SUCCESS;
}

void idx_exit()
{
	if (log_file) 
	{
		fprintf (log_file, "EXIT: close log_file ....\n");
		fclose(log_file);
	}
	else
	{
		printf ("INDEX:exit.\n");
	}

	log_file=NULL;
}

STATE idx_search(char* key, int key_len, PTR_DISK* disk_location, int* slot_cnt, int* last_slot_info)
{
	assert(key);

	int table_id=0;
	table_id= hash_func_1(key, key_len) % HT_TABLE_MOD;
	hash_2=hash_func_2(key, key_len);
	hash_3=hash_func_3(key, key_len); /* it will need */
	if (log_file)
	{
		fprintf (log_file, "Search: %-15s,  %-7d\t%-10x\t%-10x\t",key, table_id, hash_2, hash_3);
	}

	cur_ptr=ht_table[table_id];
	if (cur_ptr==IDX_NODE_NULL) 
	{
		if (log_file)
		{
			fprintf (log_file, "[failed]\n");
		}
		return IDX_NODE_NOT_EXIST;
	}

	_search_by_hash();
	if ( _cmp()!=0 )
	{
		if (log_file)
		{
			fprintf (log_file, "[failed]\n");
		}
		return IDX_NODE_NOT_EXIST;
	}

	*disk_location=_get_loc(cur_ptr);
	*last_slot_info=_get_last_info(cur_ptr);  
	*slot_cnt=_get_slot_cnt(cur_ptr);

	if (log_file)
	{
		fprintf (log_file, "disk_loc: %-15d last_info: %-15d slot_cnt: %-15d\t...[OK]\n", *disk_location, *last_slot_info, *slot_cnt);
	}
	return IDX_SUCCESS;
}
		

STATE idx_insert(char* key, int key_len, PTR_DISK disk_location, int slot_cnt, int last_slot_info)
{
	assert(key);
	int cmp;
	int table_id=0;
	PTR_KW new_ptr;

	table_id= hash_func_1(key, key_len) % HT_TABLE_MOD;
	hash_2=hash_func_2(key, key_len);
	hash_3=hash_func_3(key, key_len); /* it will need */

	if (log_file)
	{
		fprintf (log_file, "INSERT: %-15s, disk_location: %-15d\tslot_cnt: %-15d\tlast_info: %-15d\t%-10x\t%-10x ........",key, disk_location, slot_cnt, last_slot_info, hash_2, hash_3);
	}

	cur_ptr=ht_table[table_id];
	if (cur_ptr==IDX_NODE_NULL)
	{
		new_ptr=_get_free_idx_node();
		fill_idx_node(new_ptr, hash_2, hash_3, disk_location, slot_cnt, last_slot_info);
		ht_table[table_id]=new_ptr;	
		if (log_file)
		{
			fprintf (log_file, "[OK]\n");
		}
		return IDX_SUCCESS;
	}

	_search_by_hash();

	cmp=_cmp();
	if (cmp==0) 
	{
		if (log_file) fprintf (log_file, "[FAILED]\n");
		return IDX_NODE_EXIST;
	}

	new_ptr=_get_free_idx_node();
	fill_idx_node(new_ptr, hash_2, hash_3, disk_location, slot_cnt, last_slot_info);

	if (cmp<0)
	{
		_set_node_left(cur_ptr, new_ptr);
	}
	else
	{
		_set_node_right(cur_ptr, new_ptr);
	}

	if (log_file) fprintf (log_file, "[OK]\n");
	return IDX_SUCCESS;
}

/* dir==0  -->  pre_ptr==table_id */
static PTR_DISK _idx_delete(PTR_KW pre_ptr, PTR_KW cur_ptr, int dir)
{
	PTR_KW left_ptr, right_ptr;
	PTR_KW right_left_ptr, pre_right_left_ptr;
	left_ptr=_get_left(cur_ptr);
	right_ptr=_get_right(cur_ptr);

	if (left_ptr==IDX_NODE_NULL && right_ptr==IDX_NODE_NULL)
	{
		if (dir==0)
		{
			ht_table[pre_ptr]=IDX_NODE_NULL;
		}
		else if (dir==-1)
		{
			_set_node_left_null(pre_ptr);
		}
		else
		{
			_set_node_right_null(pre_ptr);
		}
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	if (left_ptr!=IDX_NODE_NULL && right_ptr!=IDX_NODE_NULL)
	{
		pre_right_left_ptr=right_left_ptr=right_ptr;
		while (_get_left(right_left_ptr)!=IDX_NODE_NULL)
		{
			//printf ("here!_2\n");
			pre_right_left_ptr=right_left_ptr;
			right_left_ptr=_get_left(pre_right_left_ptr);
		}

		if (right_left_ptr==pre_right_left_ptr)
		{
			/* case 1 */
			//printf ("here!_3\n");
			//printf ("cur_ptr:%d\tpre_ptr:%d\tdir:%d\n",_get_loc(cur_ptr), _get_loc(pre_ptr), dir);
			if (dir==0)
			{
				ht_table[pre_ptr]=right_ptr;
			}
			else if (dir==-1)
			{
				_set_node_left(pre_ptr, right_ptr);
			}
			else
			{
				_set_node_right(pre_ptr, right_ptr);	
			}
			_set_node_left(right_ptr, left_ptr);
			_put_free_idx_node(&cur_ptr);
			return _get_loc(cur_ptr);
		}	
		
		if (dir==0)
		{
			ht_table[pre_ptr]=right_left_ptr;
		}
		else if (dir==-1)
		{
			_set_node_left(pre_ptr, right_left_ptr);
		}
		else
		{
			_set_node_right(pre_ptr, right_left_ptr);
		}
		_set_node_left(pre_right_left_ptr, _get_right(right_left_ptr));
		_set_node_left(right_left_ptr, left_ptr);
		_set_node_right(right_left_ptr, right_ptr);
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	if (left_ptr!=IDX_NODE_NULL)
	{
		if (dir==0)
		{
			ht_table[pre_ptr]=left_ptr;
		}
		else if (dir==-1)
		{
			_set_node_left(pre_ptr, left_ptr);
		}
		else
		{
			_set_node_right(pre_ptr, left_ptr);
		}
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	if (right_ptr!=IDX_NODE_NULL)
	{
		if (dir==0)
		{
			ht_table[pre_ptr]=right_ptr;
		}
		else if (dir==-1)
		{
			_set_node_left(pre_ptr, right_ptr);
		}
		else
		{
			_set_node_right(pre_ptr, right_ptr);
		}
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	/* FIXME: __FILE__, __LINE__ */
	/* There is no source to release (_put_free_idx_node), so RETURN here is invalid. */
	printf ("shoule not be here.!! @idx_insert\n");
	return 0;
}


STATE idx_delete(char* key, int key_len, PTR_DISK* disk_location)
{
	int table_id=0;
	table_id=hash_func_1(key, key_len) % HT_TABLE_MOD;
	hash_2=hash_func_2(key, key_len);
	hash_3=hash_func_3(key, key_len);

	if (log_file)
	{
		fprintf (log_file, "DELETE: %15s ........", key);
	}

	cur_ptr=ht_table[table_id];
	if (cur_ptr==IDX_NODE_NULL) return IDX_NODE_NOT_EXIST;
	if (_cmp()==0) 
	{
		*disk_location=_idx_delete(table_id, cur_ptr, 0);
		if (log_file)
		{
			fprintf (log_file, " [OK]\n");
		}
		return IDX_SUCCESS;
	}	

	_search_by_hash();
	if (_cmp()!=0)
	{
		if (log_file)
		{
			fprintf (log_file, " [FAILED]\n");
		}
		return IDX_NODE_NOT_EXIST;
	}

	/*_cmp()==0 */
	*disk_location=_idx_delete(pre_ptr, cur_ptr, dir);

	if (log_file)
	{
		fprintf (log_file, " [OK]\n");
	}
	return IDX_SUCCESS;
}


/* Caller of idx_insert, idx_search, ... are considered SAFE
   Caller of idx_show are cosidered UNSAFE,
   so idx_show() need check every GLOBAL DATA
static	PTR_KW*		ht_table=NULL;  
static	IDX_NODE* 	idx_nodes=NULL;
static	PTR_KW*		idx_nodes_horizon=NULL;
static	PTR_KW*		free_idx_nodes=NULL;
static	PTR_KW*		free_idx_nodes_horizon=NULL;
*/
static void _dfs(int cur, int _dfs_level);
void  idx_show()
{
	int i;
	printf ("\n---------------------index show----------------------\n");
	
	if (ht_table==NULL || idx_nodes_horizon==NULL || free_idx_nodes_horizon==NULL)
	{
		printf ("ht_table is null? idx_nodes_horizon is null? free_idx-nodes_horizon is null?\n");
		return;
	}

	printf ("cur idx_nodes_horizon:%d\n",*idx_nodes_horizon);
	printf ("cur free_idx_nodes_horizon:%d\n",*free_idx_nodes_horizon);
	
	for (i=0; i<=HT_TABLE_MOD; i++)
	{
		if (ht_table[i]==IDX_NODE_NULL) continue;
		printf ("table_id:%d\n",i);
		_dfs(ht_table[i],0);
		printf ("\n");
	}
	printf ("-----------------------------------------------------\n");
}

static void _dfs(int cur, int _dfs_level)
{
	int i;
	for (i=0; i<_dfs_level; i++) printf ("-");
	if (cur==IDX_NODE_NULL){ printf ("\n"); return;}
	

	printf ("DFS:  [%d  %d] [%d]\n", _get_hash_2(cur), _get_hash_3(cur), _get_loc(cur) );

	_dfs(_get_left(cur), _dfs_level+1);
	_dfs(_get_right(cur), _dfs_level+1);
}



/****************************************************************************************/

static int _cmp()
{
	cur_hash_2=_get_hash_2(cur_ptr);
	if (cur_hash_2==hash_2)
	{
		cur_hash_3=_get_hash_3(cur_ptr);
		if (cur_hash_3==hash_3) return 0;
		if (hash_3 < cur_hash_3) return -1;
		return 1;
	}
	if (hash_2<cur_hash_2) return -1;
	return 1;
}

static void _search_by_hash()
{
	int cmp;
	next_ptr=IDX_NODE_NULL;
	pre_ptr=IDX_NODE_NULL;
	cmp=_cmp();
	if (cmp==0) return;
	if (cmp<0)
	{
		next_ptr=_get_left(cur_ptr);
		dir=-1;
	}
	else
	{
		next_ptr=_get_right(cur_ptr);
		dir=1;
	}
	
	while (next_ptr!=IDX_NODE_NULL)
	{
		pre_ptr=cur_ptr;
		cur_ptr=next_ptr;
		next_ptr=IDX_NODE_NULL;
		cmp=_cmp();
		if ( cmp<0 )
		{
			next_ptr=_get_left(cur_ptr);
			dir=-1;
		}
		else if (cmp > 0)
		{
			next_ptr=_get_right(cur_ptr);
			dir=1;
		}
		else break;
	}
}


static PTR_KW _get_free_idx_node()
{
	/* idx_horizon */
	if ((*free_idx_nodes_horizon)==0)
	{
		return (*idx_nodes_horizon)++;
	}
	return free_idx_nodes[--(*free_idx_nodes_horizon)];
}


static void _put_free_idx_node(PTR_KW* _ptr)
{
	free_idx_nodes[*free_idx_nodes_horizon]=*_ptr;
	(*free_idx_nodes_horizon)++;
}

/***************************************************************************************/

HASH _get_hash_2(PTR_KW ptr)
{
	return idx_nodes[ptr].hash_2;
}
HASH _get_hash_3(PTR_KW ptr)
{
	return idx_nodes[ptr].hash_3;
}

PTR_KW	_get_left(PTR_KW ptr)
{
	return idx_nodes[ptr].left_ptr;
}

PTR_KW	_get_right(PTR_KW ptr)
{
	return idx_nodes[ptr].right_ptr;
}

PTR_DISK  _get_loc(PTR_KW ptr)
{
	return idx_nodes[ptr].disk_loc;
}

int _get_slot_cnt(PTR_KW ptr)
{
	return idx_nodes[ptr].slot_cnt;
}


int  _get_last_info(PTR_KW ptr)
{
	return idx_nodes[ptr].last_slot_info;
}

void  _set_node_left(PTR_KW cur_ptr, PTR_KW new_ptr)
{
	idx_nodes[cur_ptr].left_ptr=new_ptr;
}

void  _set_node_right(PTR_KW cur_ptr, PTR_KW new_ptr)
{
	idx_nodes[cur_ptr].right_ptr=new_ptr;
}

void  _set_node_left_null(PTR_KW cur_ptr)
{
	idx_nodes[cur_ptr].left_ptr=IDX_NODE_NULL;
}

void  _set_node_right_null(PTR_KW cur_ptr)
{
	idx_nodes[cur_ptr].right_ptr=IDX_NODE_NULL;
}


void  fill_idx_node(PTR_KW cur_ptr, HASH hash_2, HASH hash_3, PTR_DISK disk_location, int slot_cnt, int last_slot_info)
{
	idx_nodes[cur_ptr].hash_2=hash_2;
	idx_nodes[cur_ptr].hash_3=hash_3;
	idx_nodes[cur_ptr].disk_loc=disk_location;
	idx_nodes[cur_ptr].slot_cnt=slot_cnt;
	idx_nodes[cur_ptr].last_slot_info=last_slot_info;
	idx_nodes[cur_ptr].left_ptr=IDX_NODE_NULL;
	idx_nodes[cur_ptr].right_ptr=IDX_NODE_NULL;	
}

/***************************************************************************************/


HASH hash_func_1(char* str, int key_len)
{
	unsigned int hash = 5381;
	while (*str)
	{
		hash += (hash << 5) + (*str++);
	}
 
	return (hash & 0x7FFFFFFF);
}

HASH hash_func_2(char* str, int key_len)
{
	int hash = 0;
	int x	= 0;
 
	while (*str)
	{
		hash = (hash << 4) + (*str++);
		if ((x = hash & 0xF0000000L) != 0)
		{
			hash ^= (x >> 24);
			hash &= ~x;
		}
	}

	return hash;
}

HASH hash_func_3(char* str, int key_len)
{
	int hash = 0;
	int i;
 
	for (i=0; *str; i++)
	{
		if ((i & 1) == 0)
		{
			hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
		}
		else
		{
			hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
		}
	}
 
	return hash;
}



